1. Field of the Invention
The present invention relates to an information preocessing apparatus such as an arithmetic operation processing element of a data flow computer using the tagged token scheme. The tagged token scheme is a processing scheme in which plurality of tokens are present on one arc of a data flow graph. In order to execute instructions without confusion, tag data (identifier data) are added to respective tokens, and operations are then performed on those tokens having an identical tag as their operand data.
2. Description of the Prior Art
Computer which is based on the data flow computation model (data flow computer), is different from conventional von Neumann type computers, in that a data flow computer has no program counter. The instruction executions of such a computer are controlled in accordance with the data-driven principle that an instruction becomes executable at a point in time when data necessary for the operation, i.e., operand data, are ready. According to this data-driven principle, when a plurality of instructions exist which have become executable by the ready state of operand data the instructions, can be executed in parallel. Consequently, it is possible to realize a higher processing capability in comparison with von Neumann type computers.
FIG. 8 is a block diagram showing a general configuration of a data flow computer for performing a parallel instruction execution with three, for example, processing elements (PE). This invention also adopts the same configuration in principle. Blocks 1.sub.1, 1.sub.2 and 1.sub.3 designate processing elements or components. A token network 2, performs routing of tokens among processing elements 1.sub.1 -1.sub.3, or between processing elements 1.sub.1 -1.sub.3 and external parts.
FIG. 9 shows a general configuration of each of the processing elements 1.sub.1 -1.sub.3, wherein 3 designates a program memory unit, and 4 a matching unit for performing the functions of waiting for the required operand data and transmitting a set of necessary operand data to an operand data processing unit 5. Then, in the operand data processing unit 5, instructions specified by the data flow program are executed. Numeral 6 designates a network inside the processing components 1.sub.1, 1.sub.2 or 1.sub.3. Network 6 performs mutual information exchanges between the program memory unit 3, the matching unit 4, the operand data processing unit 5 and the token network 2.
FIG. 10 is a signal flow graph of a fourth order digital filter. In FIG. 10, X designates an input, Y designates an output, and 7.sub.1, 7.sub.2, 7.sub.3, 7.sub.4 and 7.sub.5 show multiplications with coefficients A.sub.0, A.sub.1, A.sub.3 and A.sub.4, respectively. Additions are shown at 8.sub.1, 8.sub.2, 8.sub.3 and 8.sub.4 and 9.sub.1, 9.sub.2, 9.sub.3 and 9.sub.4 show delays.
A method to realize a fourth order digital filter by a data flow computer is explained as follows.
FIG. 11 shows a resultant data flow graph made by converting a program of the following algorithm for the fourth order digital filter of FIG. 10 by a compiler: EQU Y.sub.i-4 =A.sub.4 X.sub.i-4 +A.sub.3 X.sub.i-3 +A.sub.2 X.sub.i-2 +A.sub.1 X.sub.i-1 +A.sub.0 X.sub.i ;
wherein respective nodes correspond to instructions of a data flow computer, and data are carried out tokens which move on arcs connecting the nodes. In a conventional data flow computer, in order to realize the delay in FIG. 10, the necessary number of dummy tokens DT shown by solid circles in FIG. 11 are prepared beforehand on the nodes which require any number of dummy tokens. The positioning of these dummy tokens DT is determined at the time when the compiler converts the program into a data flow graph. (e.g. See for example, the seminar note, "Study on Latest Image Processing Processors and Development EXamples of their Application System", published by Japan Industry Engineering Center, p.46).
In order to realize the delay by using the dummy tokens as described above, the order of those tokens must be kept unchanged on respective arcs of the data flow graph. That is, tokens issued from a node must reach a destination node, keeping the same order in which they were issued. Additionally, the order of instructions shown on the node execution must keep the proper order relation with respect to first-in/first-out. Also from the point of view of constructing a data flow computer, it is necessary to have the limitation that the first-in/first-out order relation must be kept at all the positions of each relevant unit such as the token network 2, the network 6 inside the processing clement, the program memory unit 3, the matching unit 4, and the operand data processing unit 5.
The prior art apparatus has another difficult, as has been described, namely that at the time the compiler converts a program into a data flow graph, the conversion into a data program becomes possible only after the detection of the nodes at which dummy tokens must be positioned and the detection of the number of the required dummy tokens. This makes the configuration of the compiler complex. Furthermore, for execution of a program it has been necessary to position dummy tokens prior to the execution. Accordingly, additional structure for accomplishing this must be prepared in a data flow computer. And further, from the point of view of execution time of a program considerable time must be expanded to position the dummy tokens.